/**
 * 排序算法父类 Sort v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-16
 */

function getSortClassList() {
    return [
        QuickSort,
        BubbleSort,
        SelectionSort,
        InsertionSort,
        MergeSort,
        RandomQuickSort,
        CountingSort,
        RadixSort,
    ]
}

class Sort {
    static animation = null
    constructor(animation) {
        this.animation = animation
        console.log(`初始化 ${this.info()['name']}`)
    }

    info() {
        return {
            name: "未命名算法",
            available: false
        }
    }

    sort(array) {
        console.log("this method was not implement.")
        return array
    }

    doSortWithAnimation(elementId) {
        let customAttr = document.getElementById(elementId).customAttr
        let array = JSON.parse(JSON.stringify(customAttr.nodes)) // 深拷贝一个数组
        console.log(customAttr, array)
        this.sortWithAnimation(customAttr, array)
    }

    sortWithAnimation(array) {
        console.log("this method was not implement.")
        return array
    }

    /**
     * 交换数组中的两个元素
     * @param {*} array  数组
     * @param {*} index1 元素1索引
     * @param {*} index2 元素2索引
     */
    swap(array, index1, index2) {
        if (index1 < 0 || index1 >= array.length)
            throw new Error("index1索引超限")
        if (index2 < 0 || index2 >= array.length)
            throw new Error("index2索引超限")
        if (index1 == index2)
            return

        let tmp = array[index1]
        array[index1] = array[index2]
        array[index2] = tmp

        // only for test
        // console.log(Object.keys(array))
        // console.log(array, index1, index2)
    }
    swapAnimation(id, index1, index2) {
        if (index1 == index2)
            return
        animation.swapLinkedListItems(id, [index1, index2])
    }
}


/**
 * 快速排序算法 Qucik Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-16
 */
class QuickSort extends Sort {
    /**
     * step
     *
     * 1. 首先设定一个分界值，通过该分界值将数组分成左右两部分
     * 2. 将大于或等于分界值的数据集中到数组右边，小于的集中到左边
     * 3. 左右两侧的数组分别重复步骤 2.
     * 4. 完成排序
     */

    info() {
        return {
            name: "快速排序算法",
            enName: "Quick Sort",
            available: true
        }
    }

    /*
        每个（未排序）的部分
        将第一个元素设为 pivot
            存储索引 = pivot索引 +1
            从 i=pivot指数 +1 到 最右索引 的遍历
                如果 a[i] < a[pivot]
                    交换 (i, 存储索引); 存储索引++;
            交换(pivot, 存储索引 - 1)
     */
    sort(array, left, right) {
        if (typeof (left) === "undefined") left = 0
        if (typeof (right) === "undefined") right = array.length - 1

        if (right <= left)
            return array // 递归出口

        const pivot = left // 第一个元素的索引
        let p = left + 1
        for (let i = left + 1; i <= right; i++) {
            if (array[i] < array[pivot]) {
                this.swap(array, i, p)
                p++
            }
        }
        this.swap(array, pivot, p - 1)

        // 左、右分别排序（索引超限在 sort 内部进行处理，此处无需判断）
        this.sort(array, pivot, p - 2)
        this.sort(array, p, right)
        return array
    }

    sortWithAnimation(customAttr, array, left, right) {
        if (typeof (left) === "undefined") left = 0
        if (typeof (right) === "undefined") right = array.length - 1

        if (right <= left)
            return array // 递归出口

        const pivot = left // 第一个元素的索引
        let p = left + 1
        for (let i = left + 1; i <= right; i++) {
            animation.compareLinkedListItems(customAttr.id, i, pivot)
            if (array[i] < array[pivot]) {
                this.swap(array, i, p)
                this.swapAnimation(customAttr.id, i, p)
                p++
            }
        }
        this.swap(array, pivot, p - 1)
        this.swapAnimation(customAttr.id, pivot, p - 1)

        // 左、右分别排序（索引超限在 sort 内部进行处理，此处无需判断）
        this.sortWithAnimation(customAttr, array, pivot, p - 2)
        this.sortWithAnimation(customAttr, array, p, right)
        return array
    }
}


/**
 * 冒泡排序算法 Bubble Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-16
 */
class BubbleSort extends Sort {

    info() {
        return {
            name: "冒泡排序算法",
            enName: "Bubble Sort",
            available: true
        }
    }

    /*
        做
        swapped = false
        从 i = 1 到 最后一个没有排序过元素的索引-1
            如果 左边元素 > 右边元素
                交换（左边元素，右边元素）
                swapped = true; ++swapCounter（交换计数器）
        while swapped
     */
    sort(array) {
        let sortTime = 0
        let swapped
        do {
            swapped = false
            for (let i = 1; i < array.length - sortTime; i++) {
                if (array[i - 1] > array[i]) {
                    this.swap(array, i - 1, i)
                    swapped = true
                }
            }
            sortTime++
        } while (swapped)

        return array
    }

    sortWithAnimation(customAttr, array) {
        let sortTime = 0
        let swapped
        do {
            swapped = false
            for (let i = 1; i < array.length - sortTime; i++) {
                animation.compareLinkedListItems(customAttr.id, i - 1, i)
                if (array[i - 1] > array[i]) {
                    this.swap(array, i - 1, i)
                    this.swapAnimation(customAttr.id, i - 1, i)
                    swapped = true
                }
            }
            sortTime++
        } while (swapped)

        return array
    }
}


/**
 * 选择排序算法 Selection Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-16
 */
class SelectionSort extends Sort {

    info() {
        return {
            name: "选择排序算法",
            enName: "Selection Sort",
            available: true
        }
    }

    /*
        重复（元素个数-1）次
            把第一个没有排序过的元素设置为最小值
            遍历每个没有排序过的元素
                如果元素 < 现在的最小值
                    将此元素设置成为新的最小值
        将最小值和第一个没有排序过的位置交换
    */
    sort(array) {
        let minIndex
        for (let i = 0; i < array.length; i++) {
            minIndex = i
            for (let j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    this.swap(array, minIndex, j)
                }
            }
        }
        return array
    }

    sortWithAnimation(customAttr, array) {
        let minIndex
        for (let i = 0; i < array.length; i++) {
            // console.log(array)
            minIndex = i
            for (let j = i + 1; j < array.length; j++) {
                animation.compareLinkedListItems(customAttr.id, minIndex, j)
                if (array[minIndex] > array[j]) {
                    this.swap(array, minIndex, j)
                    this.swapAnimation(customAttr.id, minIndex, j)
                }
            }
        }
        return array
    }
}


/**
 * 插入排序算法 Insertion Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-18
 */
class InsertionSort extends Sort {

    info() {
        return {
            name: "插入排序算法",
            enName: "Insertion Sort",
            available: true
        }
    }

    /*
        将第一个元素标记为已排序
        对于每一个未排序的元素 X
            “提取” 元素 X
            i = 最后排序过元素的索引 到 0 的遍历
                如果当前元素 j > X
                    将排序过的元素向右移一格
            跳出循环并在此插入 X
    */
    sort(array) {
        if (array.length == 0)
            return array
        for (let i = 1; i < array.length; i++) {
            let X = array[i]
            let j = i - 1
            while (array[j] >= 0 && array[j] > X) {
                array[j + 1] = array[j]
                j--
            }
            array[j + 1] = X
        }
        return array
    }

    sortWithAnimation(customAttr, array) {
        if (array.length == 0)
            return array
        for (let i = 1; i < array.length; i++) {
            let X = array[i]
            animation.popupLinkedListItems(customAttr.id, i, {})
            let j = i - 1
            while (array[j] >= 0 && array[j] > X) {
                array[j + 1] = array[j]
                animation.exchangeLinkedListItems(customAttr.id, j + 1, j)
                j--
            }
            array[j + 1] = X
            animation.popupLinkedListItems(customAttr.id, j + 1, { popBack: true })
        }
        return array
    }
}


/**
 * 归并排序算法 Merge Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-19
 */
class MergeSort extends Sort {

    info() {
        return {
            name: "归并排序算法",
            enName: "Merge Sort",
        }
    }

    /*
        将每个元素拆分成大小为1的分区
        递归地合并相邻的分区
            遍历 i = 左侧首项位置 到 右侧末项位置
                如果左侧首项的值 <= 右侧首项的值
                    拷贝左侧首项的值
                否则： 拷贝右侧首项的值; 增加逆序数
        将元素拷贝进原来的数组中
    */
    sort(array) {
        if (array.length == 0)
            return array
        // todo
        console.log("尚未实现")
        return array
    }

    sortWithAnimation(customAttr, array) {
        if (array.length == 0)
            return array
        // todo
        console.log("尚未实现")
        return array
    }
}


/**
 * 随机快速排序算法 Random Quick Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-08-08
 */
class RandomQuickSort extends Sort {

    info() {
        return {
            name: "随机快速排序算法",
            enName: "Random Quick Sort",
            available: true
        }
    }

    /*
        每个（未排序）的部分
        将第一个元素设为 pivot
            存储索引 = pivot索引 +1
            从 i=pivot指数 +1 到 最右索引 的遍历
                如果 a[i] < a[pivot]
                    交换 (i, 存储索引); 存储索引++;
            交换(pivot, 存储索引 - 1)
    */
    sort(array, left, right) {
        if (array.length == 0)
            return array

        if (typeof left === 'undefined') left = 0
        if (typeof right === 'undefined') right = array.length - 1
        if (left < right) {
            let pivot = left
            let storeIndex = pivot + 1
            for (let i = pivot + 1; i <= right; i++) {
                if (array[i] < array[pivot]) {
                    this.swap(array, i, storeIndex)
                    storeIndex++
                }
            }
            this.swap(array, pivot, storeIndex - 1)

            this.sort(array, left, storeIndex - 2)
            this.sort(array, storeIndex, right)
        }
        return array
    }

    sortWithAnimation(customAttr, array, left, right) {
        if (array.length == 0)
            return array

        if (typeof left === 'undefined') left = 0
        if (typeof right === 'undefined') right = array.length - 1
        if (left < right) {
            let pivot = left
            let storeIndex = pivot + 1
            animation.emphasisLinkedListItems(customAttr.id, [left, right], {})
            animation.emphasisLinkedListItems(customAttr.id, [left, right], { popBack: true })
            for (let i = pivot + 1; i <= right; i++) {
                animation.compareLinkedListItems(customAttr.id, i, storeIndex)
                if (array[i] < array[pivot]) {
                    this.swap(array, i, storeIndex)
                    this.swapAnimation(customAttr.id, i, storeIndex)
                    storeIndex++
                }
            }
            this.swap(array, pivot, storeIndex - 1)
            this.swapAnimation(customAttr.id, pivot, storeIndex - 1)

            this.sortWithAnimation(customAttr, array, left, storeIndex - 2)
            this.sortWithAnimation(customAttr, array, storeIndex, right)
        }
        return array
    }
}


/**
 * 计数排序算法 Counting Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-19
 */
class CountingSort extends Sort {

    info() {
        return {
            name: "计数排序算法",
            enName: "Counting Sort",
        }
    }

    /*
        创建关键值（计数）数组
        遍历数列中的每个元素
        相应的计数器增加 1
        每轮计数，都从最小的值开始
        当计数为非零数时
        重新将元素存储于列表
        将计数减1
    */
    sort(array) {
        if (array.length == 0)
            return array
        // todo
        console.log("尚未实现")
        return array
    }

    sortWithAnimation(customAttr, array) {
        if (array.length == 0)
            return array
        // todo
        console.log("尚未实现")
        return array
    }
}


/**
 * 基数排序算法 Radix Sort  v0.1.0
 *
 * @author  coder-xiaomo
 * @date    2022-05-19
 */
class RadixSort extends Sort {

    info() {
        return {
            name: "基数排序算法",
            enName: "Radix Sort",
        }
    }

    /*
        分别给每个数位（0到9）创造1个桶（数列），共计10个
        遍历每个数位
        遍历数列中的每个元素
        将元素移至相应的桶中
        在每个桶中，从最小的数位开始
        当桶不是空的
        将元素恢复至数列中
    */
    sort(array) {
        if (array.length == 0)
            return array
        // todo
        console.log("尚未实现")
        return array
    }

    sortWithAnimation(customAttr, array) {
        if (array.length == 0)
            return array
        // todo
        console.log("尚未实现")
        return array
    }
}
